package likou.jindian;

/**
 * @author: Tangxz
 * @email: 1171702529@qq.com
 * @cate: 2020/11/26 11:28
 */
public class _03_05SortedStack {
    int[] up, down;
    int upIndex, downIndex;

    public _03_05SortedStack() {
        up = new int[5000];
        down = new int[5000];
        upIndex = downIndex = 0;
    }

    public void push(int val) {
        while (downIndex > 0 && val < down[downIndex - 1]) {
            up[upIndex++] = down[--downIndex];
        }
        while (upIndex > 0 && val > up[upIndex - 1]) {
            down[downIndex++] = up[--upIndex];
        }
        up[upIndex++] = val;
    }

    public void pop() {
        while (downIndex > 0) {
            up[upIndex++] = down[--downIndex];
        }
        if (upIndex > 0) upIndex--;
    }

    public int peek() {
        while (downIndex > 0) {
            up[upIndex++] = down[--downIndex];
        }
        return upIndex == 0 ? -1 : up[upIndex - 1];
    }

    public boolean isEmpty() {
        return upIndex == 0 && downIndex == 0;
    }
}
